package Top_Interview_Questions.Greedy;

/**
 * @Author: 吕庆龙
 * @Date: 2020/1/19 18:12
 * <p>
 * 功能描述:
 */
public class _0134 {

    public static void main(String[] args) {
        int[] gas = {1,2,3,4,5};
        int[] cost = {3,4,5,1,2};
        canCompleteCircuit(gas,cost);
    }

    /**
     * 这题看其他人的解析,也没有讲是怎样的贪心的。
     */
    public static int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;

        int total_tank = 0;
        int curr_tank = 0;
        int starting_station = 0;
        for (int i = 0; i < n; ++i) {
            total_tank += gas[i] - cost[i];
            curr_tank += gas[i] - cost[i];
            // If one couldn't get here,
            if (curr_tank < 0) {
                // Pick up the next station as the starting one.
                starting_station = i + 1;
                // Start with an empty tank.
                curr_tank = 0;
            }
        }
        return total_tank >= 0 ? starting_station : -1;
    }


    /**
     * 与53题的区别是，这题需要求的是最大子串的起始位置。代码几乎没有区别，只需要记录一下起始角标
     */
    public int canCompleteCircuit2(int[] gas, int[] cost) {
        //将问题转化为找最大子串的起始位置。
        int result = 0;
        int sum = 0;
        int hasResult = 0;//用于判断是否有跑完全程所需的油
        for (int i = 0; i < gas.length; i++) {
            hasResult +=gas[i]-cost[i];
            if(sum > 0) {
                sum += gas[i]-cost[i];
            } else {
                sum = gas[i]-cost[i];
                result = i;
            }
        }

        return hasResult>=0? result:-1;
    }


}
